package com.hardy.leecode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * Author: Hardy
 * Date:   2020/9/7
 * Description:
 **/
public class Que347 {
    public static void main(String[] args) {

        int[] nums = {1};
        int k = 1;

        System.out.println(new Solution().topKFrequent(nums, k));
    }

    static class Solution {

        public int[] topKFrequent(int[] nums, int k) {
            if (k == 1 && nums.length == 1) return nums;

            HashMap<Integer, Integer> map = new HashMap<>();

            for (int i = 0; i < nums.length; i++) {
                if (!map.containsKey(nums[i]))
                    map.put(nums[i], 0);

                map.put(nums[i], map.get(nums[i]) + 1);
            }

            ArrayList<Integer>[] hash = new ArrayList[nums.length];
            for (Integer n : map.keySet()) {
                Integer c = map.get(n) - 1;

                if (hash[c] == null) hash[c] = new ArrayList<>();
                hash[c].add(n);
            }

            int i = 0;
            int[] res = new int[k];

            outer:
            for (int j = nums.length - 1; j >= 0; j--) {
                if (hash[j] == null) continue;

                for (int m = 0; m < hash[j].size(); m++) {
                    res[i++] = hash[j].get(m);
                    if (i == k) break outer;
                }
            }
            return res;
        }
    }

    static class Solution1 {

        public int[] topKFrequent(int[] nums, int k) {
            final HashMap<Integer, Integer> map = new HashMap<>();

            for (int i = 0; i < nums.length; i++) {
                if (!map.containsKey(nums[i]))
                    map.put(nums[i], 0);

                map.put(nums[i], map.get(nums[i]) + 1);
            }

            PriorityQueue<Integer> queue = new PriorityQueue<>(k, (o1, o2) -> {
                if (map.get(o1) > map.get(o2)) return -1;
                else if (map.get(o1) < map.get(o2)) return 1;
                return 0;
            });

            for (Integer n : map.keySet()) {
                queue.offer(n);
            }

            int[] res = new int[k];
            for (int i = 0; i < k; i++) {
                res[i] = (int) queue.poll();
            }

            return res;
        }
    }
}
